import { getEventListeners } from 'events';
import { Node } from './types'
/**
 * 字典树，前缀树
 */
export default class Trie {
    private sizes = 0
    private root: Node | null = null
    /**
     * 获取单词的数量
     */
    size() {
        return this.sizes;
    }

    /**
     * 是否为空
     */
    isEmpty() {
        return this.size() === 0
    }

    /**
     * 清空该树
     */
    clear() {
        this.root = null
    }

    /**
     * 是否有该单词
     * @param str 
     */
    contains(str: string) {
        this.checkStr(str)

        // 获取该str对应的的节点
        const n = this.node(str);

        // 节点不为空并且是一个完整的单词
        return n !== null && n.word
    }

    /**
     * 添加该单词
     * @param str 
     */
    add(str: string) {
        // 校验参数
        this.checkStr(str)
        let root = this.root;
        // root为空
        if (root === null) {
            root = this.root = new Node('', null)
        }
        const len = str.length;

        let node = root;
        // 遍历字符串
        for (let i = 0; i < len; i++) {
            // 获取单个字符
            const c = str[i]

            // 还没有在children中存在      
            if (node.children[c] == null) {
                node = node.children[c] = new Node(c, node);
            } else {
                // 更换node
                node = node.children[c]
            }
        }
        // 保存该完整的单词
        node.value = str
        // 是完整的单词
        node.word = true
        // 单词数量+1
        this.sizes++;
    }

    /**
     * 删除该单词
     * @param str 
     */
    remove(str: string) {
        // 检查字符串
        this.checkStr(str)

        // 1. 获取该字符串对应的节点
        let n = this.node(str);

        // 2. 如果该节点不存在或者不是一个完整的单词, 直接返回
        if (n === null || !n.word) return

        // 获取对象的属性长度
        const getLen = (o: object) => Object.keys(o).length

        this.sizes--;

        // 当前节点还有子元素，将word和value恢复即可 e.g: doggy, dog => 删除dog
        if (getLen(n.children) > 0) {
            n.value = ''
            n.word = false
            return;
        }
        let parent = n.parent;

        // 先置为false, 防止影响后面的循环
        n.word = false

        // 3. 从当前元素开始从下往上遍历
        while (parent !== null) {
            // 1. 当前元素是一个单词结尾(多个单词前缀相同)，直接返回  e.g: dog doggy => 删除doggy
            if (n.word) {
                return;
            }
            // 从父元素删除掉自己
            delete parent.children[n.char]

            // 2. 父元素还有孩子 (多分支), 直接返回
            if ( getLen(parent.children) > 0) {
                return;
            } 

            // 更换parent
            n = parent
            parent = parent.parent;
        }
    }

    /**
     * 以prefix为前缀
     * @param prefix 
     */
    startsWith(prefix: string) {
        this.checkStr(prefix)
        return this.node(prefix) !== null
    }

    /**
     * 根据str获取最后一个字符的节点
     * 
     * e.g: cat => t对应的node
     * @param str 
     */
    private node(str: string) {
        // 获取根对象
        let root = this.root!;
        if (root === null) return null
        // 获取该单词
        const len = str.length;
        for (let i = 0; i < len; i++) {
            const c = str[i];
            // 如果没有了，直接返回
            const n = root.children[c]
            // 如果取出为空，直接返回空
            if (n == null) return null
            root = n;
        }

        return root
    }

    /**
     * 校验字符串参数
     * @param str 
     */
    private checkStr(str: string) {
        // 不是字符串或者是空的字符串
        if (typeof str !== 'string' || str == '') {
            throw new Error('非法字符串~~')
        }
    }
}